package midend.IR_Optimizer;

import midend.IR_Instruction.Calc_Instruction;
import midend.IR_Instruction.Instruction;
import midend.IR_Module;
import midend.IR_Type.IR_Const;
import midend.IR_Type.IR_Float;
import midend.IR_Type.IR_Int32;
import midend.IR_Type.IR_Type;
import midend.IR_Value.*;
import midend.IR_Optimizer.IR_Opt;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

import static midend.IR_Type.IR_Const.*;


public class Aluopt implements IR_Opt{
    private static IR_Type i32type = IR_Int32.IR_Int32();
    private static IR_Type floattype = IR_Float.IR_Float();


    public void Optimize(IR_FuncBlock function) {
        //optimizeSrem(function);
        //simplifyDiv(function);
        simplifyMul(function);
    }

    private void optimizeSrem(IR_FuncBlock function) {
        //能不能直接转 and
        LinkedList<Instruction> replaceIns = new LinkedList<>();
        LinkedList<Instruction> deletelist = new LinkedList<>();
        for(IR_BaseBlock block:function.get_bb_List()){
            for(Instruction instruction:block.get_Instruction_List()){
                if(instruction instanceof Calc_Instruction calcInstruction && calcInstruction.get_op_Type() == SREM){
                    IR_Value value = calcInstruction.get_op_index(2);
                    if(value instanceof IR_Int_Value irIntValue && isPowerOfTwo(irIntValue.get_Int_Value())){
                        IR_Value src2 = new IR_Int_Value(irIntValue.get_Int_Value() - 1,irIntValue.get_Type());
                        replaceIns.add(new Calc_Instruction(Arrays.asList(calcInstruction.get_op_index(0),calcInstruction.get_op_index(1),src2),calcInstruction.get_bb(),cAND));
                        deletelist.add(calcInstruction);
                    }
                }
            }
        }
        for(int i = 0;i < deletelist.size();i++){
            int index = deletelist.get(i).get_bb().get_Instruction_List().indexOf(deletelist.get(i));
            deletelist.get(i).get_bb().get_Instruction_List().add(index,replaceIns.get(i));
            deletelist.get(i).get_bb().get_Instruction_List().remove(deletelist.get(i));
        }
        //x mod m = x - (x / m) * m
        for (IR_BaseBlock block : function.get_bb_List()) {
            for (int count = 0; count < block.get_Instruction_List().size(); count++) {
                Instruction instruction = block.get_Instruction_List().get(count);
                if (instruction instanceof Calc_Instruction calcInstruction && calcInstruction.get_op_Type()==SREM) {
                    IR_Value left = calcInstruction.get_op_index(1);
                    IR_Value right = calcInstruction.get_op_index(2);
                    Calc_Instruction div = new Calc_Instruction(Arrays.asList(new IR_Local_Value("SREM_tmp",i32type),left, right), block, SDIV);
                    Calc_Instruction mul = new Calc_Instruction(Arrays.asList(new IR_Local_Value("SREM_tmp",i32type),div.get_op_index(0), right), block, MUL);
                    Calc_Instruction sub = new Calc_Instruction(Arrays.asList(calcInstruction.get_op_index(0),left, mul.get_op_index(0)), block, SUB);
                    block.get_Instruction_List().add(count, sub);
                    block.get_Instruction_List().add(count, mul);
                    block.get_Instruction_List().add(count, div);
                    instruction.remove();
                }
            }
        }
    }

    //判断一个给定的整数是否为 2 的幂
    public static boolean isPowerOfTwo(int number) {
        if (number < 1) {
            return false;
        }
        return (number & (number - 1)) == 0;
    }

    //整数的2的幂次
    public static int powerOfTwo(int number) {
        if (number < 1) {
            throw new IllegalArgumentException("Number must be greater than 0");
        }

        int count = 0;
        while (number > 1) {
            number >>>= 1; // 使用无符号右移，确保不会引入符号位
            count++;
        }
        return count;
    }

    // 函数的作用是找出一个整数在二进制表示中所有 1 的位置
    public static ArrayList<Integer> countOnesInBinary(int number) {
        ArrayList<Integer> positions = new ArrayList<>();
        int position = 0;

        while (number != 0) {
            if ((number & 1) == 1) {
                positions.add(position);
            }
            position++;
            number = number >>> 1; // 无符号右移，检查下一位
        }
        return positions;
    }


    public static void simplifyMul(IR_FuncBlock function) {
        for (IR_BaseBlock block : function.get_bb_List()) {
            for (int count = 0; count < block.get_Instruction_List().size(); count++) {
                Instruction instruction = block.get_Instruction_List().get(count);
                if (instruction instanceof Calc_Instruction && ((Calc_Instruction) instruction).get_op_Type() == IR_Const.MUL) {
                    IR_Value left = instruction.get_op().get(1);
                    IR_Value right = instruction.get_op().get(2);
                    if (left instanceof IR_Int_Value && !(right instanceof IR_Int_Value)) {
                        //-1
                        if (((IR_Int_Value) left).get_Int_Value() == -1) {
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction newCalc = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, new IR_Int_Value(0, i32type), right)), block, IR_Const.SUB);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, newCalc);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp1);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) left).get_Int_Value())) { //2的整数次幂
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction newCalc = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, right, new IR_Int_Value(powerOfTwo(((IR_Int_Value) left).get_Int_Value()), i32type))), block, IR_Const.SHL);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, newCalc);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp1);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) left).get_Int_Value() + 1)) { //2的整数次幂-1
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, right, new IR_Int_Value(powerOfTwo(((IR_Int_Value) left).get_Int_Value()+1), i32type))), block, IR_Const.SHL);
                            Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, tmp1, right)), block, IR_Const.SUB);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, sub);
                            block.get_Instruction_List().add(index, shl);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp2);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) left).get_Int_Value() - 1)) { //2的整数次幂+1
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, right, new IR_Int_Value(powerOfTwo(((IR_Int_Value) left).get_Int_Value()-1), i32type))), block, IR_Const.SHL);
                            Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, tmp1, right)), block, IR_Const.ADD);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, sub);
                            block.get_Instruction_List().add(index, shl);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp2);
                            instruction.remove();
                        } else if (((IR_Int_Value) left).get_Int_Value() > 0) {
                            ArrayList<Integer> numbers;
                            if ((numbers = countOnesInBinary(((IR_Int_Value) left).get_Int_Value())).size() == 2) {
                                IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                                IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                                IR_Value tmp3 = new IR_Local_Value("mul",i32type);
                                Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, right, new IR_Int_Value(numbers.get(0), i32type))), block, IR_Const.SHL);
                                Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, right, new IR_Int_Value(numbers.get(1), i32type))), block, IR_Const.SHL);
                                Calc_Instruction add = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp3, tmp1, tmp2)), block, IR_Const.ADD);
                                int index = block.get_Instruction_List().indexOf(instruction);
                                block.get_Instruction_List().add(index, add);
                                block.get_Instruction_List().add(index, sub);
                                block.get_Instruction_List().add(index, shl);
                                function.replaceUseInFunc(instruction.get_op().get(0), tmp3);
                                instruction.remove();
                            }
                        }
                    } else if (right instanceof IR_Int_Value && !(left instanceof IR_Int_Value)) {
                        //与上面同理
                        if (((IR_Int_Value) right).get_Int_Value() == -1) {
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction newCalc = new Calc_Instruction(Arrays.asList(tmp1, new IR_Int_Value(0, i32type), left), block, IR_Const.SUB);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, newCalc);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp1);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value())) { //2的整数次幂
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction newCalc = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, left, new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value()), i32type))), block, IR_Const.SHL);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, newCalc);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp1);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value() + 1)) { //2的整数次幂-1
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, left, new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value()+1), i32type))), block, IR_Const.SHL);
                            Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, tmp1, left)), block, IR_Const.SUB);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, sub);
                            block.get_Instruction_List().add(index, shl);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp2);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value() - 1)) { //2的整数次幂+1
                            IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                            IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                            Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, left, new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value()-1), i32type))), block, IR_Const.SHL);
                            Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, tmp1, left)), block, IR_Const.ADD);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, sub);
                            block.get_Instruction_List().add(index, shl);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp2);
                            instruction.remove();
                        } else if (((IR_Int_Value) right).get_Int_Value() > 0) {
                            ArrayList<Integer> numbers;
                            if ((numbers = countOnesInBinary(((IR_Int_Value) right).get_Int_Value())).size() == 2) {
                                IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                                IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                                IR_Value tmp3 = new IR_Local_Value("mul",i32type);
                                Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, left, new IR_Int_Value(numbers.get(0), i32type))), block, IR_Const.SHL);
                                Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, left, new IR_Int_Value(numbers.get(1), i32type))), block, IR_Const.SHL);
                                Calc_Instruction add = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp3, tmp1, tmp2)), block, IR_Const.ADD);
                                int index = block.get_Instruction_List().indexOf(instruction);
                                block.get_Instruction_List().add(index, add);
                                block.get_Instruction_List().add(index, sub);
                                block.get_Instruction_List().add(index, shl);
                                function.replaceUseInFunc(instruction.get_op().get(0), tmp3);
                                instruction.remove();
                            }
                        }
                    }
                }
            }
        }
    }

    public static void simplifyDiv(IR_FuncBlock function) {
        for (IR_BaseBlock block : function.get_bb_List()) {
            for (int count = 0; count < block.get_Instruction_List().size(); count++) {
                Instruction instruction = block.get_Instruction_List().get(count);
                if (instruction instanceof Calc_Instruction && ((Calc_Instruction) instruction).get_op_Type() == IR_Const.SDIV) {
                    IR_Value left = instruction.get_op().get(1);
                    IR_Value right = instruction.get_op().get(2);
                    if (right instanceof IR_Int_Value) {
                        if (((IR_Int_Value) right).get_Int_Value() == -1) {
                            IR_Value tmp1 = new IR_Local_Value("div",i32type);
                            Calc_Instruction sub = new Calc_Instruction(Arrays.asList(tmp1, new IR_Int_Value(0, i32type), left), block, IR_Const.SUB);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, sub);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp1);
                            instruction.remove();
                        } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value())) {
                            IR_Value tmp1 = new IR_Local_Value("div",i32type);
                            Calc_Instruction newCalc = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, left, new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value()), i32type))), block, IR_Const.ASHR);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, newCalc);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp1);
                            instruction.remove();
                        } else if ((Math.abs(((IR_Int_Value) right).get_Int_Value()) & Math.abs((((IR_Int_Value) right).get_Int_Value() - 1))) == 0) { //绝对值
                            int number = countOnesInBinary(((IR_Int_Value) right).get_Int_Value()).get(0);
                            IR_Value tmp1 = new IR_Local_Value("div",i32type);
                            IR_Value tmp2 = new IR_Local_Value("div",i32type);
                            IR_Value tmp3 = new IR_Local_Value("div",i32type);
                            IR_Value tmp4 = new IR_Local_Value("div",i32type);
                            Calc_Instruction ashr = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1, left, new IR_Int_Value(31, i32type))), block, IR_Const.ASHR);
                            Calc_Instruction lshr = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2, tmp1, new IR_Int_Value( 32 - number,i32type))), block, IR_Const.LSHR);
                            Calc_Instruction add = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp3, tmp2, left)), block, IR_Const.ADD);
                            Calc_Instruction ashr2 = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp4, tmp3, new IR_Int_Value(number, i32type))), block, IR_Const.ASHR);
                            int index = block.get_Instruction_List().indexOf(instruction);
                            block.get_Instruction_List().add(index, ashr2);
                            block.get_Instruction_List().add(index, add);
                            block.get_Instruction_List().add(index, lshr);
                            block.get_Instruction_List().add(index, ashr);
                            function.replaceUseInFunc(instruction.get_op().get(0), tmp4);
                            instruction.remove();
                        }
                        //else { //一般立即数
//                            int num = Math.abs(((ConstInt) right).getValue());
//                            long largeNum = ((long) 1 << 31) - (((long) 1 << 31) % num) - 1;
//                            long p = 32;
//                            while ((1L << p) <= largeNum * (num - (1L << p) % num)) {
//                                p++;
//                            }
//
//                            long m = (((1L << p) + (long) num - ((long) 1 << p) % num) / (long) num);
//                            int n = (int) ((m << 32) >>> 32);
//                            int shift = (int) (p - 32);
//                            ALUInstr mul = new ALUInstr(IntegerType.i32, left, new ConstInt(IntegerType.i32, n), InstrType.MUL, block);
//                            mul.setIs64();
//                            ALUInstr ashr = new ALUInstr(IntegerType.i32, mul, new ConstInt(IntegerType.i32, 32), InstrType.ASHR, block);
//                            ALUInstr ashr2 = new ALUInstr(IntegerType.i32, ashr, new ConstInt(IntegerType.i32, shift), InstrType.ASHR, block);
//                            ALUInstr ashr3 = new ALUInstr(IntegerType.i32, ashr2, new ConstInt(IntegerType.i32, 31), InstrType.ASHR, block);
//                            ALUInstr sub = new ALUInstr(IntegerType.i32, ashr2, ashr3, InstrType.SUB, block);
//                            ALUInstr sub2 = null;
//                            if (((ConstInt) right).getValue() < 0) {
//                                sub2 = new ALUInstr(IntegerType.i32, new ConstInt(IntegerType.i32, 0), sub, InstrType.SUB, block);
//                            }
//                            ALUInstr result = (sub2 == null) ? sub : sub2;
//                            int index = block.getInstrList().indexOf(instruction);
//                            if (sub2 != null) {
//                                block.getInstrList().add(index, sub2);
//                            }
//                            block.getInstrList().add(index, sub);
//                            block.getInstrList().add(index, ashr3);
//                            block.getInstrList().add(index, ashr2);
//                            block.getInstrList().add(index, ashr);
//                            block.getInstrList().add(index, mul);
//                            instruction.replaceUse(result);
//                            instruction.remove();
//                        }
                    }
                }
            }
        }
    }



    public static ArrayList<Instruction> simplifyMul(Calc_Instruction instruction, IR_BaseBlock block) {
        ArrayList<Instruction> simplify = new ArrayList<>();
        //优化 乘法指令 操作数的获取 主要是针对常量乘法的优化
        IR_Value ans =  ((Calc_Instruction) instruction).get_op_index(0);
        IR_Value left = ((Calc_Instruction) instruction).get_op_index(1);
        IR_Value right = ((Calc_Instruction) instruction).get_op_index(2);
        if (left instanceof IR_Int_Value && !(right instanceof IR_Int_Value)) { // 为什么不能两个都是整数常量？因为这种情况会直接进行常量传播处理
            //-1 的乘法转化为 减法
            if (((IR_Int_Value) left).get_Int_Value() == -1) {
                Calc_Instruction newAlu = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,new IR_Int_Value(0,i32type), right)),block, IR_Const.SUB);
                simplify.add(newAlu);
            } else if (isPowerOfTwo(((IR_Int_Value) left).get_Int_Value())) { //2的整数次幂 转化为移位
                Calc_Instruction newAlu = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,right,new IR_Int_Value(powerOfTwo(((IR_Int_Value) left).get_Int_Value()),i32type))),block, IR_Const.SHL);
                simplify.add(newAlu);
            } else if (isPowerOfTwo(((IR_Int_Value) left).get_Int_Value() + 1)) { //2的整数次幂-1  转化为移位和减法
                IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1,right, new IR_Int_Value(powerOfTwo(((IR_Int_Value) left).get_Int_Value() + 1),i32type))), block, IR_Const.SHL);
                Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2,ans, right)), block, IR_Const.SUB);
                simplify.add(shl);
                simplify.add(sub);
            } else if (isPowerOfTwo(((IR_Int_Value) left).get_Int_Value() - 1)) { //2的整数次幂+1 转化为移位和加法
                IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1,right, new IR_Int_Value(powerOfTwo(((IR_Int_Value) left).get_Int_Value() - 1),i32type))), block, IR_Const.SHL);
                Calc_Instruction add = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2,tmp1, right)), block, IR_Const.ADD);
                simplify.add(shl);
                simplify.add(add);
            } else if (((IR_Int_Value) left).get_Int_Value() > 0) {
                ArrayList<Integer> numbers;
                //对于只有能够转化成两位的 如 6 110   10 1010  两次移位一次加法是实现
                if ((numbers = countOnesInBinary(((IR_Int_Value) left).get_Int_Value())).size() == 2) {
                    IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                    IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                    Calc_Instruction shl1 = new Calc_Instruction( new ArrayList<>(Arrays.asList(tmp1,right, new IR_Int_Value( numbers.get(0),i32type))), block, IR_Const.SHL);
                    Calc_Instruction shl2 = new Calc_Instruction( new ArrayList<>(Arrays.asList(tmp2,right, new IR_Int_Value( numbers.get(1),i32type))),block, IR_Const.SHL);
                    Calc_Instruction add = new Calc_Instruction( new ArrayList<>(Arrays.asList(ans,tmp1, tmp2)), block, IR_Const.ADD);
                    simplify.add(shl1);
                    simplify.add(shl2);
                    simplify.add(add);
                }
            }
        } else if (right instanceof IR_Int_Value && !(left instanceof IR_Int_Value)) {
            //与上面同理
            if (((IR_Int_Value) right).get_Int_Value() == -1) {
                Calc_Instruction newAlu = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,new IR_Int_Value(0,i32type), left)), block, IR_Const.SUB);
                simplify.add(newAlu);
            } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value())) {
                Arrays.asList(ans,left,powerOfTwo(((IR_Int_Value) right).get_Int_Value()), block, IR_Const.SHL);
                Calc_Instruction newAlu = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,left,new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value()),i32type))), block, IR_Const.SHL);
                simplify.add(newAlu);
            } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value() + 1)) {
                IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1,left,new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value() + 1),i32type))), block,IR_Const.SHL);
                Calc_Instruction sub = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,tmp1,left)), block, IR_Const.SUB);
                simplify.add(shl);
                simplify.add(sub);
            } else if (isPowerOfTwo(((IR_Int_Value) right).get_Int_Value() - 1)) {
                IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                Calc_Instruction shl = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1,left,new IR_Int_Value(powerOfTwo(((IR_Int_Value) right).get_Int_Value() - 1),i32type))), block,IR_Const.SHL);
                Calc_Instruction add = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,tmp1,left)), block, IR_Const.SUB);
                simplify.add(shl);
                simplify.add(add);
            } else if (((IR_Int_Value) right).get_Int_Value() > 0) {
                ArrayList<Integer> numbers;
                if ((numbers = countOnesInBinary(((IR_Int_Value) right).get_Int_Value())).size() == 2) {
                    IR_Value tmp1 = new IR_Local_Value("mul",i32type);
                    IR_Value tmp2 = new IR_Local_Value("mul",i32type);
                    Calc_Instruction shl1 = new Calc_Instruction( new ArrayList<>(Arrays.asList(tmp1,left, new IR_Int_Value( numbers.get(0),i32type))), block, IR_Const.SHL);
                    Calc_Instruction shl2 = new Calc_Instruction( new ArrayList<>(Arrays.asList(tmp2,left, new IR_Int_Value( numbers.get(1),i32type))), block, IR_Const.SHL);
                    Calc_Instruction add = new Calc_Instruction( new ArrayList<>(Arrays.asList(ans,tmp1, tmp2)), block, IR_Const.ADD);
                    simplify.add(shl1);
                    simplify.add(shl2);
                    simplify.add(add);
                }
            }
        }
        if (simplify.size() == 0) {
            simplify.add(instruction);
        }
        return simplify;
    }


    //有符号整数除法（SDIV）的优化转换，
    // 将除法运算替换为一系列更高效的乘法、移位和加减操作。它专门处理除数为常量的情况，属于编译器优化中的常量除法转换
    public static ArrayList<Instruction> simplifyDiv(Calc_Instruction instruction, IR_BaseBlock block) {
        IR_Value ans = instruction.get_op_index(0);
        IR_Value left = instruction.get_op_index(1);
        IR_Value right = instruction.get_op_index(2);
        ArrayList<Instruction> instructions = new ArrayList<>();
        if (instruction.get_op_Type() == IR_Const.SDIV && right instanceof IR_Int_Value) {
            int num = Math.abs(((IR_Int_Value) right).get_Int_Value());
            long largeNum = ((long) 1 << 31) - (((long) 1 << 31) % num) - 1;
            long p = 32;
            while ((1L << p) <= largeNum * (num - (1L << p) % num)) {
                p++;
            }

            long m = (((1L << p) + (long) num - ((long) 1 << p) % num) / (long) num);
            int n = (int) ((m << 32) >>> 32);
            int shift = (int) (p - 32);
            IR_Value tmp1 = new IR_Local_Value("div",i32type);
            Calc_Instruction mul = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp1,left,new IR_Int_Value(n,i32type))), block, IR_Const.MUL);
            mul.setIs64();
            IR_Value tmp2 = new IR_Local_Value("div",i32type);
            Calc_Instruction ashr = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp2,tmp1,new IR_Int_Value(32,i32type))), block,  IR_Const.ASHR);
            Calc_Instruction add = null;
            IR_Value tmp3 = new IR_Local_Value("div",i32type);
            if (m >= 0x80000000L) {
                add = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp3,tmp2,left)), block, IR_Const.ADD);
            }
            IR_Value tmp4 = new IR_Local_Value("div",i32type);
            Calc_Instruction ashr2 = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp4,(add == null)?tmp2:tmp3,new IR_Int_Value(shift,i32type))), block, IR_Const.ASHR);
            IR_Value tmp5 = new IR_Local_Value("div",i32type);
            Calc_Instruction ashr3 = new Calc_Instruction(new ArrayList<>(Arrays.asList(tmp5,tmp4,new IR_Int_Value(31,i32type))), block, IR_Const.ASHR);
            IR_Value tmp6 = new IR_Local_Value("div",i32type);
            Calc_Instruction sub = new Calc_Instruction( new ArrayList<>(Arrays.asList(ans,tmp4,tmp5)), block,IR_Const.SUB);

            Calc_Instruction sub2 = null;
            if (((IR_Int_Value) right).get_Int_Value() < 0) {
                sub2 = new Calc_Instruction(new ArrayList<>(Arrays.asList(ans,new IR_Int_Value(0,i32type), ans)), block,IR_Const.SUB);
            }
            Calc_Instruction result = (sub2 == null) ? sub : sub2;

            instructions.add(mul);
            instructions.add(ashr);
            if (add != null) {
                instructions.add(add);
            }
            instructions.add(ashr2);
            instructions.add(ashr3);
            instructions.add(sub);
            if (sub2 != null) {
                instructions.add(sub2);
            }
        }
        return instructions;
    }

}
